package 图.并查集;

import 板子.UnionFindSets;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/8 16:51
 */
public class lc547省份数量 {





    public int solve(int [][]martix){

        int N = martix.length;
        UnionFindSets.UnionFind unionFind = new UnionFindSets.UnionFind(N);

        for(int i = 0;i < martix.length;i++){
            for(int j = i + 1;j < martix.length;j++){
                if(martix[i][j] == 1){ // 说明 i 和 j 相连, 那反过来 j 和 i 也相连, 所以只需要判断 ,对角线以上就行!
                    unionFind.union(i,j);
                }
            }
        }
        return unionFind.sets();
    }






    static class UF{
        private int parent[]; // 父节点 数组  parent[i] = val 表示 i 号几点的 父节点是  val
        private int size[]; //  size[i] 表示 i 所在的圈子的  **节点个数**
        private int sets; // 多少个 连通分量


        public UF(int n){
            parent = new int[n];
            size = new int[n];
            sets = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }

        }
        public int find(int x){
            if(parent[x] == x) {
                return x;
            }
           return  parent[x] = find(parent[x]);
        }

        public void union(int i,int j){
            int ip = find(i), jp = find(j);
            if(ip != jp){
                parent[ip] = jp;
                size[ip] += size[jp];
                sets--;
            }
        }
    }

}
